class Solution
{
public:
    int rob(vector<int> &nums)
    {
        int n = nums.size();
        if (n == 1)
        {
            return nums[0];
        }
        vector<vector<int>> dp(2, vector<int>(n));
        dp[0][0] = 0;
        dp[0][1] = nums[1];
        dp[1][0] = dp[1][1] = nums[0];
        for (int i = 2; i < n; ++i)
        {
            dp[0][i] = max(dp[0][i - 1], dp[0][i - 2] + nums[i]);
            dp[1][i] = max(dp[1][i - 1], dp[1][i - 2] + nums[i]);
        }
        dp[1][n - 1] = dp[1][n - 2];
        return max(dp[0][n - 1], dp[1][n - 1]);
    }
};